package 题目集.hash;

//https://www.acwing.com/problem/content/1232/
/**
 * 在朴素算法中
 * 我们是通过枚举所有区间终点r。
 * 再枚举r左侧的所有起点l,(r-1到1)。
 * 判断这些S[r]-S[l]是否为k的倍数。是则ans++
 * 这样的时间复杂度是O(n^2)
 *
 * 而我们并不需要枚举所有的l。
 * 只需要找到(S[r]-S[l])%k==0 等同于(S[r]%k-S[l]%k)%k==0，即S[r]%k==S[l]%k的总类个数
 * 即只需要统计在r之前，有多少个S[l]%k与S[r]%k相同，既可以算出S[k]区间内所有符合条件的值。
 * 我们可以用哈希表来存储S[l]%k的个数。
 * 这样的时间复杂度是O(n)
 */
import java.util.Scanner;

/**
 *	暴力思路:
 *		对a求一个前缀和,固定j枚举j左侧的i.寻找所有(sum[j]-sum[i-1])%k==0的位置
 * 	优化:
 		对于上面的式子,可以转化为:sum[j]%k-sum[i-1]%k==0,相当于找到左侧与sum[j]%余数相同sum[i]个数
 		所以可以维护一个余数词频的哈希表,每次询问直接去找与自己余数相同的个数.
 *
 */
public class K倍区间哈希表与同余原理 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] pre=new int[n+1];
        int[] count=new int[k];
        count[0]=1;
        long res=0;
        for (int i = 1; i <= n; i++) {
            pre[i]=sc.nextInt();
            pre[i]%=k;
            pre[i]+=pre[i-1];
            pre[i]%=k;
            res+=count[pre[i]];
            count[pre[i]]++;
        }
        System.out.println(res);
    }
}
